package com.leecode.xiehf.page_04;

import com.leecode.Printer;

import java.util.*;

/**
 * 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
 * <p>
 * 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/largest-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution_0179 extends Printer {

    public static void main(String[] args) {
        Solution_0179 solution = new Solution_0179();
        String s = solution.largestNumber(new int[]{3, 30, 30, 34, 5, 9});
        print(s);
    }

    public String largestNumber(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        StringBuilder sb = new StringBuilder();
        for (int i = nums.length - 1; i >= 0; i--) {
            sb.append(nums[i]);
        }
        if (sb.charAt(0) == '0') {
            return "0";
        }
        return sb.toString();
    }

    public void quickSort(int[] nums, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        int key = nums[left];

        while (left < right) {
            while (right > left && egt(nums[right], key)) {
                right--;
            }
            nums[left] = nums[right];
            while (left < right && elt(nums[left], key)) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;
        quickSort(nums, leftIndex, left - 1);
        quickSort(nums, right + 1, rightIndex);
    }

    private boolean egt(int a, int b) {
        String m = String.valueOf(a);
        String n = String.valueOf(b);
        return (m + n).compareTo(n + m) >= 0;
    }

    private boolean elt(int a, int b) {
        String m = String.valueOf(a);
        String n = String.valueOf(b);
        return (m + n).compareTo(n + m) <= 0;
    }
}
